In digital communications, a channel code is used to protect data sent over a channel for storage or retrieval in the presence of noise or other errors. A channel code typically achieves the protection by employing forward error correction or bit interleaving (or both). Channel codes typically comprise convolutional codes or block codes. Block codes accept k information bits and generate n coded bits. Block codes are primarily used for error detection or correction in data transmissions.
A linear block code is an error-correcting code for which any linear combination of codewords is another codeword of the code. An (n, k) linear block coder generates an n-bit coded output for each k-bit input, where n is greater than k. The additional n minus k bits introduced into the bit stream by the linear block coder are added to detect errors and/or remove errors at the receiver. For example, a (6, 3) linear block coder generates a 6-bit coded output for each 3-bit input. There are eight possible 3-bit inputs, and there are 64 possible 6-bit coded outputs that can be generated by the linear block coder. FIG. 1A illustrates an exemplary conventional linear block coder 120. As shown in FIG. 1A, the linear block coder 120 receives one of eight possible 3-bit inputs 110 and, for a given input, generates a corresponding 6-bit coded output 130. The particular exemplary linear block code shown in FIG. 1A demonstrates the property that the final three output bits are equal to the three input bits.
At the receiver, a channel decoder performs an inverse operation of the channel coder. In other words, the channel decoder attempts to map each set of incoming n bits to the original set of k bits that was transmitted. The channel decoder uses the additional n minus k bits introduced into the bit stream by the linear block coder 120 to detect and/or remove errors that occur during transmission.
While existing linear block decoding techniques can effectively detect and/or remove errors that occur during transmission, they suffer from a number of limitations, which if overcome, could further improve the reliability and efficiency of linear block decoding techniques. It can be shown that in an additive white Gaussian noise (AWGN) channel; the maximum likelihood (ML) criterion is the optimal reception method from a bit-error-rate (BER) perspective. The computation complexity of an ML technique, however, is prohibitive, as it requires measuring the Euclidean distance between the received vector and all possible codewords. The codeword with the minimum distance is determined to be the most likely vector that minimizes the BER.
A need therefore exists for methods and apparatus for ML-based linear block decoding that demonstrate a reduced computational complexity, relative to the above-described conventional techniques.